package psn.zjk.career.interview.algorithm.sort;

import java.io.*;
import java.util.HashMap;
import java.util.LinkedList;

/**
 * @USER white
 * @DATETIME 2021/1/13 23:44
 */
public class Lru {

    HashMap<Integer, Integer> map = new HashMap();
    LinkedList<Integer> keys = new LinkedList<>();
    int size;

    public Lru(int size) {
        this.size = size;
    }

    public void put(int k, int v) {
        map.put(k, v);
        if (keys.size() == size) {
            keys.removeLast();
            keys.addFirst(k);
        }
    }


    public int get(int k) {
        if (map.containsKey(k)) {
            keys.remove(new Integer(k));
            keys.addFirst(k);
        }
        return map.get(k);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        String s = null;
        String s1 = bufferedReader.readLine();
        Lru lru = new Lru(Integer.parseInt(s1));
        BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));
        while ((s = bufferedReader.readLine()) != null) {
            try {
                String[] s2 = s.split(" ");
                if (s2.length == 3 && "p".equals(s2[0])) {
                    lru.put(Integer.parseInt(s2[1]), Integer.parseInt(s2[2]));
                } else if (s2.length == 2 && "g".equals(s2[0])) {
                    Integer i = lru.get(Integer.parseInt(s2[1]));
                    if (i == null) {
                        bufferedWriter.write("nil" );
                    } else {
                        bufferedWriter.write("" + i);
                    }
                    bufferedWriter.flush();
                    bufferedWriter.newLine();
                    bufferedWriter.flush();
                }

            } catch (Exception e) {
                bufferedWriter.write("wrong args");
                bufferedWriter.flush();
                bufferedWriter.newLine();
                bufferedWriter.flush();
            }
        }

    }
}
